
if __name__ == "__main__":
    # determine the number of units of water that would be trapped in a landscape
    # defined by the the waterTable array

    waterTable = [ 3, 5, 0, 3, 7, 1, 4, 2, 9, 8, 7, 3, 2, 9, 1, 6, 2, 3, 5, 4, 8, 1, 4, 7, 1]

    maxHeight = max(waterTable)
    totalWater = 0
    leftMaxIndex = -1
    rightMaxIndex = -1

    index = 0
    maxFromEdge = 0
    while waterTable[index] != maxHeight:
        maxFromEdge = max(maxFromEdge, waterTable[index])
        totalWater += maxFromEdge - waterTable[index]
        index += 1

    leftMaxIndex = index
    index = len(waterTable) - 1
    maxFromEdge = 0
    while waterTable[index] != maxHeight:
        maxFromEdge = max(maxFromEdge, waterTable[index])
        totalWater += maxFromEdge - waterTable[index]
        index -= 1

    rightMaxIndex = index
    for index in range(leftMaxIndex + 1, rightMaxIndex):
        totalWater += maxHeight - waterTable[index]

    print(totalWater)

    # Alternatively...
    # We'll start with the total volume of the bounding rect for the water table,
    # then subtract all of the area we know not to be filled.
    maxHeight = max(waterTable)
    totalWater = maxHeight * len(waterTable)

    # subract the volume of the steps
    totalWater -= sum(waterTable)

    index = 0;
    maxFromEdge = 0
    while waterTable[index] != maxHeight:
        # This position and everything to the right of here will be filled in at 
        # least up to maxFromEdge
        maxFromEdge = max(maxFromEdge, waterTable[index])
        # We know how high the water is here, so we can subtract all of the space
        # that is not filled 
        totalWater -= (maxHeight - maxFromEdge)
        index += 1

    index = len(waterTable) - 1
    maxFromEdge = 0
    while waterTable[index] != maxHeight:
        maxFromEdge = max(maxFromEdge, waterTable[index])
        totalWater -= (maxHeight - maxFromEdge)
        index -= 1

    print(totalWater)



